package SubjectHashTable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

/**
 * 难度：中等
 * 
 * 18. 四数之和
 * 	给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
 * 	使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 * 
 * 注意：
 * 	答案中不可以包含重复的四元组。
 * 
 * 示例：
 * 	给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * 	满足要求的四元组集合为：
 * 	[
 * 	  [-1,  0, 0, 1],
 * 	  [-2, -1, 1, 2],
 * 	  [-2,  0, 0, 2]
 * 	]
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FourSum fs = new FourSum();
		System.out.println(fs.fourSum(new int[] { 1, 0, -1, 0, -2, 2 },0));
	}
	// 自己写
	public List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> lists = new ArrayList<>();
		if(nums==null||nums.length<4) {
			return lists;
		}
		int n=nums.length;
		Arrays.sort(nums);
		for(int first=0;first<n-3;first++) {
			//判断是否和上一个数相同
			if(first>0&&nums[first]==nums[first-1]) {
				continue;
			}
			//两个数无论取什么值，四数之和一定大于 target
			if(nums[first]+nums[first+1]+nums[first+2]+nums[first+3]>target) {
				break;
			}
			//两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮
			if(nums[first]+nums[n-3]+nums[n-2]+nums[n-1]<target) {
				continue;
			}
			for(int second=first+1;second<n-2;second++) {
				//判断是否和上一个数相同
				if(second>first+1&&nums[second]==nums[second-1]) {
					continue;
				}
				//两个数无论取什么值，四数之和一定大于 target
				if(nums[first]+nums[second]+nums[second+1]+nums[second+2]>target) {
					break;
				}
				//两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮
				if(nums[first]+nums[second]+nums[n-2]+nums[n-1]<target) {
					continue;
				}
				int third=second+1;
				int fourth=n-1;
				while(third<fourth) {
					
					if(nums[first]+nums[second]+nums[third]+nums[fourth]>target) {
						fourth--;
					}else if(nums[first]+nums[second]+nums[third]+nums[fourth]<target) {
						third++;
					}else if(nums[first]+nums[second]+nums[third]+nums[fourth]==target) {
						
						lists.add(Arrays.asList(nums[first],nums[second],nums[third],nums[fourth]));
						
						//判断是否和下一个数相同
						while(third<fourth&&nums[third]==nums[third+1]) {
							third++;
						}
						third++;
						//判断是否和下一个数相同
						while(third<fourth&&nums[fourth]==nums[fourth-1]) {
							fourth--;
						}
						fourth--;
						
					}
				}
			}
		}
		return lists;
    }
}
